7311. Вставить скобки

Милхаузу необходимо на завтра решить задачу, и ему нужна Ваша помощь. Вот задача:

Задана строка, состоящая из скобок. Необходимо превратить ее в правильную строку, вставляя как можно меньшее количество скобок в любую позицию (удалять или изменять существующие скобки нельзя). Правильной является строка, которая удовлетворяет следующим правилам:

· Пустая строка правильная.

· Если s правильная, то (s) также правильная.

· Если s и t правильные, то их конкатенация st правильная.

Например, "(()())", "" и "(())()" правильные строки, а "())(", "()(" и ")" - нет.

Вход. Задана строка из скобок, которая содержит от 1 до 50 символов включительно.

Выход. Вывести наименьшее количество скобок, которое следует вставить для того чтобы входная строка стала правильной.

Пример входа	Пример выхода
(()(()	2

РЕШЕНИЕ

стек

Анализ алгоритма

Воспользуемся счетчиком balance, который будет подсчитывать баланс открытых и закрытых скобок. Как только balance станет отрицательным, необходимо вставить одну дополнительную открывающуюся скобку для того чтобы обработанный префикс строки стал правильным.

По окончании обработки строки необходимо также добавить balance закрывающихся скобок.

Пример

Для того чтобы входная строка стала правильной, необходимо добавить balance + res = 2 + 2 = 4 скобки.

Реализация алгоритма

В переменной res подсчитываем количество раз, которое переменная balance станет отрицательной.

balance = res = 0;

while(scanf("%c",&c), c != '\n')

{

Считаем баланс скобок. Обрабатываем случай, когда он становится отрицательным.

balance += (c == '(') ? 1 : -1;

if (balance < 0)

{

res++;

balance = 0;

}

}

Выводим ответ.

printf("%d\n",res + balance);

Java реализация – символьный массив

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

char[] s = con.nextLine().toCharArray();

int balance = 0, res = 0;

for(int i = 0; i < s.length; i++)

{

balance += (s[i] == '(') ? 1 : -1;

if (balance < 0)

{

res++;

balance = 0;

}

}

System.out.println(res + balance);

con.close();

}

}

Java реализация – строка

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

String s = con.nextLine();

int balance = 0, res = 0;

for(int i = 0; i < s.length(); i++)

{

balance += (s.charAt(i) == '(') ? 1 : -1;

if (balance < 0)

{

res++;

balance = 0;

}

}

System.out.println(res + balance);

con.close();

}

}